package com.dyz.leetcode._20_dynamicProgramming._140;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class wordBreak01 {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, new HashSet<>(wordDict), 0);

    }

    private List<String> dfs(String s, Set<String> wordDict, int i){
        List<String> res = new ArrayList<>();
        if(i==s.length()){
            res.add("");
            return res;
        }

        for (int end = i+1; end <=s.length() ; end++) {
            String word = s.substring(i, end);
            if(!wordDict.contains(word)){continue;}

            List<String> list = dfs(s, wordDict, end);
            for (String str:list) {
                res.add(word + (str.equals("")?"":" ")+str);
            }
        }
        return res;
    }

}
